//
// Created by francklinson on 2021/10/12 AT 9:52.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    /**
     * 每个数字都只能出现一次
     * 那么 保留这个数列的最大最小值
     * 遇到“I”时，放入当前的最小值
     * 遇到“D”时，放入当前的最大值
     * 就一定能保证满足目标
     * @param s
     * @return
     */
    vector<int> diStringMatch(string s) {
        int n = static_cast<int>(s.size());
        int left = 0,right = n;
        vector<int>ans;
        for (int i = 0; i <n ; ++i) {
            // 遇到I，放入当前数列的最小值
            if (s[i]=='I'){
                ans.push_back(left++);
            } else{
                ans.push_back(right--);
            }
        }
        ans.push_back(left);
        return ans;
    }
};

int main() {
    Solution solution;
    vector<int> ans = solution.diStringMatch("DOI");
    for (auto x: ans)
        cout << x << " ";
    cout << endl;
    return 0;
}

